package com.xsherl.leetcode.solution;

import com.xsherl.leetcode.base.ListNode;

public class PartitionList {

    /**
     * 建立左右两个链表，然后遍历原链表，如果小于 x 就放在左链表中，否则放在右链表
     * 最后组合两个链表
     */
    public ListNode partition(ListNode head, int x) {
        ListNode leftHead = new ListNode(), rightHead = new ListNode();
        ListNode node = head, left = leftHead, right = rightHead;
        while (node != null){
            if (node.val < x){
                ListNode t = node.next;
                node.next = left.next;
                left.next = node;
                node = t;
                left = left.next;
            } else {
                ListNode t = node.next;
                node.next = right.next;
                right.next = node;
                node = t;
                right = right.next;
            }
        }
        left.next = rightHead.next;
        return leftHead.next;
    }

    public static void main(String[] args) {
        ListNode head = ListNode.build(1,4,3,2,5,2);
        int x = 4;
        ListNode partition = new PartitionList().partition(head, x);
        System.out.println(partition);
    }

}
